"""
看到项目中有一个A*算法,跟图有关,挺有意思.在游戏中很常用.
所以看到网上一个python实现,现在来研究一下.
这个算法主要是跟 dijikstra算法比较.他是启发型的但是保证找到最优解.速度比地理特斯拉算法要快很多!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
"""
"""
需要进行抽象化的有：
    节点属性
        x y 坐标  
        父节点  
        g(离起点距离) -- g = 从起点沿着已生成的路径到一个给定方格的移动开销
        h(离终点距离) -- h = 从给定方格到目的方格的估计移动开销（曼哈顿方法）
        
    地图属性
        高度 
        宽度  
        数据(数据中有可通行路径与障碍两种)

A_star :
    open_list -- 表示已经走过的点
        存放待测试的点，刚开始有 start 加入 list，后面每一个 current 的相邻点（不能位于 colse_list 中且不是终点）要放到 open_list 中
         
    close_list -- 存放已经探测过的点，不必再进行探测
        存放已测试的点，已经当过 current 的点，就放到 close_list 中 
        
    current -- 现在正在测试的点
        要计算 current 周围的点的代价 f 经过 current 后要放到 close_list中 将 openlist 代价 f 最小的 node 当作下一个 current
        f(寻路消耗) = g + h
    
    start_point -- 起点
    
    end_point -- 终点
"""
"""
初始化地图  open_list close_list node

将 start_point 点放入 open_list 中

while（未达到终点）：
    取出 open_list 中的点 将这个点设置为 current 并放入close_list 中
    for node_near in （current 的临近点）
        if（current的临近点 node_near 不在 close_list 中且不为障碍）：
            计算 node_near 的 f（f = g + h）大小
        if( node_near 不在 open_list 中)   # 表示这个节点可以进行探索.
            将 node_near 放入 open_list，并将其父节点设置为 current 然后将f值设置为计算出的f值
        else if( node_near 在 open_list 中)
            if（计算出的 f 大于在 open_list 中的 f）
                不动作
            else if（计算出的 f 小于等于在 open_list 中的 f）
                将 open_list 中的 node_near 的f值更新为计算出的新的更小的 f 值 并将父节点设置为 current
        返回并继续循环


之前的算法没有,在对角线和直线上加不同的权重,就导致最优解可能会走斜线来到达直线就能到达的目标.
所以加上对角权重即可.
"""
import sys
import copy
import itertools


# 将地图中的点抽象化成类
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    # 定义了类的等于行为
    def __eq__(self, other):
        if self.x == other.x and self.y == other.y:
            return 1
        else:
            return 0


# 通过列表实现的地图的建立  类c语言数组？
class map_2d:
    def __init__(self, height, width):
        self.height = height
        self.width = width

        self.data = [[0 for _ in range(width)] for _ in range(height)]

    # 展示地图
    def map_show(self):
        for i in range(self.height):
            for j in range(self.width):
                print(self.data[i][j], end=" ")
            print("")

    # 设置障碍，也就是填入1
    def obstacle(self, obstacle_x, obstacle_y):
        # 注意游戏地图一定要有边缘,所以最后的2b地图周围一圈必须都是1才行.
        # 这样 obstacle 中也包含了是否超出边界的处理过程.
        self.data[obstacle_x][obstacle_y] = 1

    # 设置起点和终点
    def end_draw(self, point):
        # 字符 6 表示开始和结束点
        self.data[point.x][point.y] = 6


# 设置 node，这些 node 作为地图中点的抽象，往 list 中放
class Node:
    def __init__(self, point, endpoint, g):
        self.point = point  # 自己当前的坐标
        self.endpoint = endpoint  # 目标结束点的坐标
        self.father = None  # 父节点
        self.g = g  # g 值，g 值在用到的时候会重新计算

        # 结束点到当前节点的距离 * 10
        self.h = (abs(endpoint.x - point.x) + abs(endpoint.y - point.y)) * 10  # 计算 h 值
        self.f = self.g + self.h

    # 寻找临近点，然后返回这个点抽象之后的 node
    def search_near(self, ud, rl):  # up down right left
        # ud, rl 都是 -1 or 1 表示周围的点
        nearpoint = Point(self.point.x + rl, self.point.y + ud)

        # 下面为什么要加1 我们把权重写在这个地方. 就是后面+1,下面我修改这个为对角衰减类型
        # nearnode = A_star.Node(nearpoint, self.endpoint, self.g+1 )

        # 我修改的对角衰减类型.
        if 0 in [ud, rl]:
            # 上下左右
            nearnode = Node(nearpoint, self.endpoint, self.g + 1)
        else:
            # 对角线
            nearnode = Node(nearpoint, self.endpoint, self.g + 1.4)

        return nearnode


# A*算法的实现
class A_star:
    def __init__(self, start_point, end_point, map):  # 需要传输到类中的，在此括号中写出
        self.path = []
        self.close_list = []  # 存放已经走过的点
        self.open_list = []  # 存放需要尽心探索的点
        self.current = 0  # 现在的 node
        self.start_point = start_point  # 起点
        self.end_point = end_point  # 终点
        self.map = map  # 所在地图

    def select_current(self):
        # 这个select 体现了贪婪,因为先计算最小的min,然后走 f值最小的那个节点.
        min = 10000000
        node_temp = 0

        # 找到open表中 f值最小的节点.把它当作下一步应该走到的位置！并且就这么走
        # 在记录表中记录下这个一个步骤.
        for ele in self.open_list:
            if ele.f < min:
                min = ele.f
                node_temp = ele

        self.path.append(node_temp)
        self.open_list.remove(node_temp)
        self.close_list.append(node_temp)
        return node_temp

    def isin_openlist(self, node):
        for opennode_temp in self.open_list:
            if opennode_temp.point == node.point:
                return opennode_temp
        return 0

    def isin_closelist(self, node):
        for closenode_temp in self.close_list:
            if closenode_temp.point == node.point:
                return 1
        return 0

    def is_obstacle(self, node):
        if self.map.data[node.point.x][node.point.y] == 1:
            return 1
        return 0

    # 整个算法的核心函数就这个一个!!!!!!!!!
    def near_explore(self, node):
        # 对周围8个方块进行逐个判断,所以是8个类似的部分!!!!!!!
        for ud, rl in itertools.product([-1, 0, 1], [-1, 0, 1]):
            """ 
            ud = -1, rl = -1, 0, 1
            ud = 0, rl = -1, 1
            ud = 1, rl = -1, 0, 1
            """
            if ud == 0 and rl == 0:  # 当前节点
                continue
            node_temp = node.search_near(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
            if node_temp.point == self.end_point:
                return 1  # 返回1表示已经不用再搜索了,返回0表示还没到终点.
            elif self.isin_closelist(node_temp):  # closelist表示搜索过的点.
                pass
            elif self.is_obstacle(node_temp):  # 表示不能走的点,也pass掉.
                pass
            elif self.isin_openlist(node_temp) == 0:  # 之前 open_list 作更新.
                node_temp.father = node
                self.open_list.append(node_temp)
            else:  # 下行是动态规划的公式核心.  # 也就是 node 的 f 值更新而已.
                if node_temp.f < (self.isin_openlist(node_temp)).f:
                    self.open_list.remove(self.isin_openlist(node_temp))
                    node_temp.father = node
                    self.open_list.append(node_temp)
        return 0


def create_map():
    # 建图并设立障碍
    ss = map_2d(40, 50)

    # 地图边界
    for i in range(50):
        ss.obstacle(0, i)
    for i in range(50):
        ss.obstacle(39, i)
    for i in range(40):
        ss.obstacle(i, 0)
    for i in range(40):
        ss.obstacle(i, 49)

    # 地图障碍
    for i in range(25):
        ss.obstacle(4, i)
    for i in range(5, 35):
        ss.obstacle(11, i)
    for i in range(20, 38):
        ss.obstacle(i, 8)
    for i in range(20, 35):
        ss.obstacle(37, i)
    ss.obstacle(8, 6)
    ss.obstacle(6, 8)
    ss.obstacle(6, 15)
    ss.obstacle(9, 10)

    # 起点终点
    start_point = Point(1, 3)
    end_point = Point(38, 45)

    ss.end_draw(end_point)
    ss.end_draw(start_point)

    # 展示初始地图
    ss.map_show()

    return ss, start_point, end_point


def create_map2():
    # 建图并设立障碍
    ss = map_2d(40, 50)

    # 地图边界
    for i in range(50):
        ss.obstacle(0, i)
    for i in range(50):
        ss.obstacle(39, i)
    for i in range(40):
        ss.obstacle(i, 0)
    for i in range(40):
        ss.obstacle(i, 49)

    # 地图障碍
    for i in range(33, 37):
        ss.obstacle(9, i)
    for i in range(36, 39):
        ss.obstacle(10, i)
    for i in range(38, 41):
        ss.obstacle(11, i)

    for i in range(40, 42):
        ss.obstacle(12, i)
    for i in range(41, 43):
        ss.obstacle(13, i)
    for i in range(42, 44):
        ss.obstacle(14, i)
    for i in range(43, 45):
        ss.obstacle(15, i)
    for i in range(43, 45):
        ss.obstacle(16, i)
    for i in range(43, 45):
        ss.obstacle(17, i)
    for i in range(45):
        ss.obstacle(18, i)
    for i in range(9, 50):
        ss.obstacle(2, i)

    for i in range(5, 35):
        ss.obstacle(11, i)
    for i in range(20, 38):
        ss.obstacle(i, 8)
    for i in range(20, 35):
        ss.obstacle(37, i)
    ss.obstacle(8, 6)
    ss.obstacle(6, 8)
    ss.obstacle(6, 15)
    ss.obstacle(9, 10)

    # 起点终点
    start_point = Point(1, 3)
    end_point = Point(38, 45)

    ss.end_draw(end_point)
    ss.end_draw(start_point)

    # 展示初始地图
    ss.map_show()

    return ss, start_point, end_point


def start():
    ss, start_point, end_point = create_map()

    # ss2用于画最优解.
    ss2 = copy.deepcopy(ss)  # 注意这个地方因为是对象所以要重新开内存来赋值才避免冲突.

    # 初始化设置A*
    a_star = A_star(start_point, end_point, ss)
    start_node = Node(start_point, end_point, 0)
    a_star.open_list.append(start_node)

    flag = 0  # 到达终点的标志位
    m = 0  # 步数统计

    # 进入循环
    while flag != 1:
        a_star.current = a_star.select_current()  # 从 open_list 中选取一个 node
        flag = a_star.near_explore(a_star.current)  # 对选中的 node 进行周边探索
        m = m + 1
        print(m)

    # 画出地图路径
    for node_path in a_star.path:
        ss.end_draw(node_path.point)
    ss.map_show()

    print("上面打印的地图里面的6只是表示所有探索过的位置,而不是真正最优解走的路径.")

    print("下面打印最优解:")
    endNode = a_star.open_list[-1]
    save = []
    tmp = endNode
    while tmp.father is not None:
        ss2.end_draw(tmp.point)
        tmp = tmp.father
    ss2.map_show()
    # for i in a_star.open_list:
    #     print(i.point.x, i.point.y)


if __name__ == '__main__':
    start()
